package graph;

import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Graph {
	public static long numNodes, numEdges; // ? Let me worry about DS later
	public long numEdgesAdded;
	public boolean [][] Nodes;
	public static long [] maxValues;
	public static List<graphNode> ListOfPotentials;
	
    public Graph(){
        //Dont Worry i will make graph and set potentials

		//readGraph(GraphFileName);
		//traingulate();
		//print();
		//readPotential(PotentialFileName);             
    }
    
	public Graph(String GraphFileName,String PotentialFileName){
		readGraph(GraphFileName);
		traingulate();
		print();
		readPotential(PotentialFileName);
	}
	
	public void readGraph(String GraphFileName){
		try {
	        FileReader File = new FileReader(GraphFileName);
			Scanner in = new Scanner(File);
	        
            numNodes = in.nextLong();
            numEdges = in.nextLong();
            
            /* Init */
            numEdgesAdded = 0;
            Nodes = new boolean [(int)numNodes][(int)numNodes];
            maxValues = new long [(int)numNodes];
            for(long i=0;i<numNodes;i++)
            	maxValues[(int)i] = 0;
            for(long i=0;i<numNodes;i++)
                for(long j=0;j<numNodes;j++)
                	Nodes[(int)i][(int)j] = false;
            
            /* Read Maximum Value a node can take */
            for(long i=0;i<numNodes;i++){
            	long node = in.nextInt();
            	long val  = in.nextInt();
            	maxValues[(int)node] = val;
            }
            
            /* Read Edges */
            for(long i=0;i<numEdges;i++){
            	long node1 = in.nextInt();
            	long node2 = in.nextInt();
            	Nodes[(int)node1][(int)node2] = Nodes[(int)node2][(int)node1] = true; 
            }

            in.close();
		
       }
	     catch (Exception e) {
	            e.printStackTrace();
	     }
	}
	
	public void readPotential(String PotentialFilaName){
		
		ListOfPotentials = new ArrayList<graphNode>();
		
		try {
	        FileReader File = new FileReader(PotentialFilaName);
			Scanner in = new Scanner(File);
			
			graphNode temp = null;
			
			while(in.hasNext()){
				String nodes = in.nextLine();
				String val[] = nodes.split(" ");
				
				//for(String s : val)
					//System.err.println(s);
				
				if(val[0].equalsIgnoreCase("#")){		// new clique 
					if(temp != null)
						ListOfPotentials.add(temp);
					temp = new graphNode();
					for(int i = 1; i<val.length; i++)
						temp.nodesPresent.add(Integer.parseInt(val[i]));
					
					continue;
				}
				
				List<Integer> variableVal = new ArrayList<Integer>();
				for(int i = 0; i<val.length - 1; i++){
					variableVal.add(Integer.parseInt(val[i]));
				}
				
				double value = Double.parseDouble(val[val.length - 1]);
				temp.values.put(variableVal, value);
			}	
			ListOfPotentials.add(temp);	
				
			System.err.println("Tables Obtained ");
			for(int i = 0; i<ListOfPotentials.size(); i++){
				System.err.println("The Nodes present in phi "+i+" are :");
				for(int j: ListOfPotentials.get(i).nodesPresent)
					System.err.print(j+" ");
				System.err.println();
				
				for(List<Integer> keys : ListOfPotentials.get(i).values.keySet()){
					for(int j : keys)
						System.err.print(j+" ");
					System.err.println(ListOfPotentials.get(i).values.get(keys));
				
				}
			
			}	

		}
		catch(Exception e){
			e.printStackTrace();
		}
	
	}
	
		
	public boolean isEdge(long node1, long node2){
		return Nodes[(int)node1][(int)node2] ;
	}
	
	public ArrayList<Long> getNeighbours(long node){
		ArrayList<Long >  nbrs = new ArrayList<Long>();
		for(long i=0;i<numNodes;i++)
			if(Nodes[(int)node][(int)i])
				nbrs.add(i);
		return nbrs;
	}
	
	public boolean isSimplicial(long node){
		/* Take the neighbours of the node
		   Take a node too
		   Check the above node forms a complete Graph */
		ArrayList<Long >  nodes = getNeighbours(node);
		nodes.add(node);
		for(long i=0;i<nodes.size();i++){
			long node1 = nodes.get((int)i);
			for(long j=0;j<nodes.size();j++){
				long node2 = nodes.get((int)j);
				if( (node1!=node2) && isEdge(node1, node2)==false)
					return false;
			}
		}
		return true;
	}

	public void connectNbrs(long node, boolean eliminated[]){
		/* Take the neighbours of the node, which are not eliminated already
		   make the non-eliminated neighbours form a complete graph */
		ArrayList<Long >  nbrs = new ArrayList<Long>();
		for(long i=0;i<numNodes;i++)
			if(Nodes[(int)node][(int)i]==true && eliminated[(int)i]==false)
				nbrs.add(i);
		
		for(long i=0;i<nbrs.size();i++){
			long node1 = nbrs.get((int)i);
			for(long j=0;j<nbrs.size();j++){
				long node2 = nbrs.get((int)j);
				if( (node1!=node2) && isEdge(node1, node2)==false){
					Nodes[(int)node1][(int)node2] = Nodes[(int)node2][(int)node1] = true;
					numEdgesAdded++;
				}					
			}
		}
	}
	
	public void traingulate(){
		/*eliminated to keep track nodes which are eliminated */
		boolean eliminated [] = new boolean [(int)numNodes];
		
		for(long i=0;i<numNodes;i++)
			eliminated[(int)i] = true;
		
		ArrayList<Long> nodesToCheck = new ArrayList<Long>();
		
		/* Include non-simplicial Vertices */
		for(long i=0;i<numNodes;i++)
			if(isSimplicial(i) == false){
				nodesToCheck.add(i);
				eliminated[(int)i]=false;
			}
		
		
		while(nodesToCheck.size() != 0){	
			/*Pick a first node, eliminate it */
			
			int nodeTmp=-1;
			long minDeg = 100000000000000L;
			for(int i=0;i<nodesToCheck.size();i++){
				long nodeA=nodesToCheck.get(i);
				long deg = 0;
				for(int j=0;j<nodesToCheck.size();j++){
					long nodeB = nodesToCheck.get(j);
					if(i==j) 
						continue;
					else if(isEdge(nodeA, nodeB))
						deg++;
				}
				if(minDeg > deg){
					minDeg = deg;
					nodeTmp = i; /* index to delete */
				}
			}
				
			long node = nodesToCheck.get(nodeTmp);
			nodesToCheck.remove(nodeTmp);
			
			eliminated[(int)node]=true;
			connectNbrs(node,eliminated);
		}
		
	}

	public void traingulate001(){
		/*eliminated to keep track nodes which are eliminated */
		boolean eliminated [] = new boolean [(int)numNodes];
		for(long i=0;i<numNodes;i++)
			eliminated[(int)i] = true;
		
		ArrayList<Long> nodesToCheck = new ArrayList<Long>();
		
		/* Include non-simplicial Vertices */
		for(long i=0;i<numNodes;i++)
			if(isSimplicial(i) == false){
				nodesToCheck.add(i);
				eliminated[(int)i]=false;
			}
		
		
		while(nodesToCheck.size() != 0){	
			/*Pick a first node, eliminate it */
			
			long node = nodesToCheck.get(0);
			nodesToCheck.remove(0);
			
			eliminated[(int)node]=true;
			connectNbrs(node,eliminated);
		}
		
	}
	
	public void print(){
		System.err.print("*");
		for(long j=0;j<numNodes;j++)
			System.err.print("\t"+j);
		System.err.print("\n");

		for(long i=0;i<numNodes;i++){
			System.err.print(i);
			for(long j=0;j<numNodes;j++)
				System.err.print("\t"+(Nodes[(int)i][(int)j]?1:0));
			System.err.print("\n");
		}
		
		System.err.println("Edges Added " + numEdgesAdded);
	}
	
}

